The invention relates generally to memory storage and, more particularly, to forming data cache directories with reduced bits.
It is known in the prior art to form cache memories with cache lines comprising a range of about 8 bytes to 512 bytes. Each cache line has a “tag” that is used to access it, and a set of bits that indicate the state of the line. These bits may be maintained in a cache “directory”.
One prior art technique of reducing the storage requirements for tags uses a sectored cache. Such a cache may be organized into large cache lines, each of which may have several subsectors that may share one common tag. The subsectors have valid bits that may be used to indicate which of the sectors contain valid data. On an access miss, if the common tag of a sector matches the address tag, but the appropriate subsector is invalid, then that subsector alone is made valid by fetching the corresponding data and storing it there. On an access miss to a sector where the common tag does not match the address tag, the entire sector may be discarded or evicted, the common tag may be set to the tag of the missed address, and the appropriate subsector fetched and stored in the cache. This and other exemplary techniques may be disclosed in a publication titled Sector Cache Design and Performance, by Jeffrey Rothman and Alan Smith, in Proceedings of MASCOTS 2000.
The number of address tags required for tag storage may be proportional to the size of a cache. As physical memory grows, the space needed for tag storage may require more address bits and larger memory to store each address tag.
FIG. 2A shows an example of tag usage in the prior art wherein every cache line in a set has the same number of bits for the tag. This example depicts an 8-way set associative cache with 4096 sets and 128-byte lines. In this example, the access address is 50 bits in size, and due to the cache organization, a 31-bit tag 215 that corresponds to data of a cache line. The number of bits used for all the tags in one set of data is therefore 31 times the associativity or 248 bits. Thus, in such prior art tag organizations, as physical memory grows, the space needed for storing tag bits also grows proportionally.
Hence, there is a need for organizing and accessing cache to reduce the amount of storage required to store cache tags.